package com.zk.algorithm.array;

import com.zk.algorithm.Utils;
import com.zk.algorithm.annotation.Easy;
import com.zk.algorithm.annotation.LeetCodeExplore;

import java.util.Arrays;

/**
 * @author zk
 */
@LeetCodeExplore
@Easy
public class MoveZeroes {

    // Input: [0,1,0,3,12]
    // Output: [1,3,12,0,0]
    //
    // 不能改变非 0 元素的顺序

    // 基本想法：两个指针，把所有非零元素移动到数组左端
    // 一个指针 idx，指住最左边，已经填充好的元素
    // 另外一个指针 i 在前面探路，只探非 0 元素
    public void moveZeroes(int[] nums) {
        int idx = 0;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[idx++] = nums[i];
            }
        }

        Arrays.fill(nums, idx, nums.length, 0);
    }

    public static void main(String...args) {
        int[] nums = new int[]{0,1,0,3,12};
        new MoveZeroes().moveZeroes(nums);
        Utils.println(nums);

        nums = new int[]{0,0,0,1,4,0,2};
        new MoveZeroes().moveZeroes(nums);
        Utils.println(nums);

        nums = new int[]{1};
        new MoveZeroes().moveZeroes(nums);
        Utils.println(nums);
    }

}
